package bill.study.algorithms.searchingSorting;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class GeneralizedBinarySearch {
	
	public static void main(String [] args){
		
		Integer [][] array = new Integer[][]{
				{1,2,3,4,5},
				{6,7,8,9,10},
				{11,12,13,14,15},
				{16,17,18,19,20},
				{21,22,23,24,25},
				{26,27,28,29,30},
				{31,32,33,34,35},
				{36,37,38,39,40}
				
				
		};
		LinkedList ll = new LinkedList();
	
		Integer target = 24;
	Indices result=	findInTwoDimensionArray(array, target, theComparator);
	System.out.println(" the indices of the target is : " + result);
	}
	
	
	public static <T > Indices findInTwoDimensionArray( T[][] array, T target, Comparator<? super T> c){
		if(array == null){
			throw new IllegalArgumentException("The array parameter cannot be null");
		}
		
		if(target == null){
			throw new IllegalArgumentException("The array target cannot be null");
		}
		
		int height =array.length;
		int width = array[0].length;
		
		
		for(int h = 0, w = 0; h< height && w < width; h ++ , w++){
		    // binary search horizontally
			printArray(array[h], w, width-1);
			int indexW = Arrays.binarySearch(array[h], w, width, target, c);
			if(  indexW>=0){
				return new Indices(h,indexW );
			}
			else{
				// build a temp array
				List<T> list = new ArrayList<T>();
				for(int hh = h + 1; hh < height; hh ++ ){
					list.add(array[hh][w]);
				}
				T [] tempArray = (T []) list.toArray();
				printArray(tempArray, 0, tempArray.length -1);
				
				// binary search vertically
				int indexH = Arrays.binarySearch(tempArray, target, c);
				if(indexH >=0){
					return new Indices(indexH +h +1, w);
				}
			}
		}
		
		return new Indices(-1, -1);
	}
	
	
	
	/**
	 * Indices is immutable
	 * @author yangliu
	 *
	 */
	public final static class Indices{
		private int columnIndex;
		private int rowIndex;
		private Indices(int cIndex, int rIndex){
			this.columnIndex = cIndex;
			this.rowIndex = rIndex;
		}
		public int getColumnIndex() {
			return columnIndex;
		}
		public int getRowIndex() {
			return rowIndex;
		}
		
		public String toString(){
			return "[" + columnIndex + "," + rowIndex + "]";
		}
	}
	
	
	private static class SimpleIntegerComparator implements Comparator<Integer>{
		public int compare(Integer o1, Integer o2) {
			return o1.compareTo(o2);
		};
	}
	
	// the instance will be reused.
	private static SimpleIntegerComparator theComparator = new SimpleIntegerComparator();

	
	private static <T> void printArray(T[] arr, int from, int to){
		System.out.println("****************");
		for(int i = from; i <=to; i ++)
		System.out.print(arr[i]+",");
		System.out.println("-------");
		
	}
}
